1. Field of the Invention
The present invention relates to digital video signal processing and, in particular, to computer-implemented processes and apparatus for reduction of visual artifacts in block-based video compression/decompression systems.
2. Description of the Related Art
Motion estimation is commonly utilized by video encoders in signal processing techniques that compress successive frames of digital video data (xe2x80x9cvideo framesxe2x80x9d). When these video frames are to be transmitted via a communication medium of limited bandwidth, or are to be stored in a storage medium having limited storage capacity, it is often desirable to first compress the digital data which represents each frame, so as to reduce the amount of data that needs to be transmitted.
Motion estimation is one of the most computationally intense of the various techniques utilized to compress data. Motion estimation techniques exploit the temporal correlation that often exists between consecutive video frames, in which there is a tendency for objects or image features to move from one location to another on a display device as image refreshing is accomplished from frame to frame.
For instance, frame 1 may contain an object, and frame 2 may contain a set of pixels corresponding to the same object spatially displaced by a few pixels from the location in frame 1. If frame 1 is transmitted to and received by a pixel processor or video processor (which performs any necessary decompression or other decoding), frame 2 may be transmitted including the complete pixel data corresponding to the object. Instead, motion vectors (i.e. xe2x80x9cpointersxe2x80x9d) and difference data are sent representing frame 2 (which are typically easily compressible using standard techniques). These motion vectors and difference data may be utilized by the receiving video processor when decoding the received video frame 2 to reproduce the object from frame 1 at a new location within frame 2. Since such motion vectors and difference data can be represented with fewer bits than the pixels that comprise the object, fewer bits need to be transmitted (or stored) in order to recreate the object in frame 2.
The motion estimation procedure may be performed at the encoder level by comparing given regions or blocks within a current video frame to many regions or blocks within the previous video frame. The process of comparing a given block of one frame to a block of another frame is called xe2x80x9cblock matching.xe2x80x9d Blocks are matched by determining a xe2x80x9ccomparison measurementxe2x80x9d between any given pair of blocks. A comparison measurement corresponds to some form of indication of a degree of xe2x80x9cdifferencexe2x80x9d between the two regions. What is often done is to look at some or all of the hue and luminance values of the pixels within a block and to use a standard criterion (such as mean absolute error or mean square error) to accomplish accurate block matching. By using the block corresponding to the lowest comparison measurement a best block match is found. The block in the previous video frame may be utilized as described above by the video decoder to reproduce a xe2x80x9cduplicatexe2x80x9d block in the current video frame.
In most systems, the above-mentioned motion vectors are transmitted for closely-matched block along with some xe2x80x9cdifferencexe2x80x9d data for the respective blocks that characterizes difference levels between the xe2x80x9cmatchedxe2x80x9d blocks either at the pixel level or as some sort of an average over the regions of the respective blocks. This difference data is usually easily compressible since the relative magnitudes of the differences are usually quite small.
In performing block comparisons, a number of pixels from the previous video frame are accessed for each block of the current video frame that is subjected to motion estimation. In most general purpose video processing systems, the bit maps corresponding to the previous and current video frame pixels are stored in general purpose memory connected to the video processor through a bus. For each block matching procedure the video processor must access the memory many times, which may constitute a high amount of traffic on the bus and a high number of memory accesses. Because of the limited bandwidth of the bus by which the memory is accessed, these memory accesses can tie up use of the bus and memory and thus slow down overall operation of the video processing system.
To avoid this problem, the video processor performing the motion estimation step may contain, for example, a dedicated, special-purpose memory space to store the two video frames being compared so that there is less traffic on the bus. However, such a special-purpose memory space is often unavailable, unfeasible, or otherwise not desired because of the extra complexity of such a special-purpose memory. The special-purpose memory space may be too costly. Further, even a special purpose memory space may be accessed so often during block matching that the video processor may be slowed down.
Typically, a digital video frame is divided into 8xc3x978 blocks and 16xc3x9716 macroblocks comprising four 8xc3x978 blocks each. These macroblocks are also referred to as xe2x80x9ctiles.xe2x80x9d The above-mentioned block-matching is usually done with whole tiles. Sometimes the 8xc3x978 blocks within the tiles are simultaneously processed conveniently with parallel processing equipment that work best on 8xc3x978 blocks.
When xe2x80x9cmatchedxe2x80x9d tiles are put in their new locations in the current frame in accordance with their respective location vectors, and when the data in these tiles is adjusted in accordance with the corresponding xe2x80x9cdifferencexe2x80x9d magnitudes, the resulting new frame inevitably has some error buildup along the edges of the tiles. This error is compounded with each additional frame transmitted by the above-described technique until a new complete xe2x80x9creferencexe2x80x9d frame is transmitted (typically every tenth frame). The gradual buildup of error results in what those skilled in the art refer to as xe2x80x9cblockyxe2x80x9d visual artifacts. These artifacts can be quite degrading to the overall quality of the transmitted image.
It is accordingly an object of this invention to improve upon the techniques of the known art and to provide a method and apparatus that substantially reduces tile boundary artifacts that would otherwise exist.
Further objects and advantages of this invention will become apparent from the Detailed Description of preferred embodiments which follows.
The invention is an apparatus and method for reducing observable blockiness in decoded images that are encoded using block-based video compression. In the invention, images are divided into blocks using tiling patterns that are changed from frame-to-frame. Typically, a first image is received and divided into a plurality of blocks using a first tiling pattern. The first image is encoded to generate encoded signals for the first image. A second image is received and is divided into a plurality of blocks using a second tiling pattern different from the first tiling pattern. The blocks of the second image are encoded to generate encoded signals for the second image. A decoder uses the tiling pattern corresponding to the tiling pattern of the encoded image to decode the encoded image, wherein the edges of the blocks of the decoded images preferably are distinctly located from image to image.
In a preferred embodiment, images are padded with a border around the periphery of the image. The padding can be used to pad a relatively smaller block, for example, one less than full or standard block size, which, when performing the tiling pattern shifting or staggering of the invention, may be located on the periphery of the image. The padding extends the smaller block""s dimensions such that it may be processed as a full size or standard block.